package org.basic.algorithm.simple.offer;

import java.util.Arrays;

/**
 * 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
 * <p>
 * 示例 1:
 * 输入: n = 2
 * 输出: [0,1,1]
 * <p>
 * 示例 2:
 * 输入: n = 5
 * 输出: [0,1,1,2,1,2]
 *
 * @author LiKun
 * @date 2021/10/27 15:32
 */
public class CalBinaryNumber {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(countBits(5)));
    }

    public static int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            result[i] = result[i >> 1] + (i & 1);
        }

        return result;
    }
}
